package com.cty._04_Optimization._48_LongestSubstringWithoutDup;

/**
 * @Auther: cty
 * @Date: 2020/7/19 8:59
 * @Description: 面试题48：最长不含重复字符的子字符串
 * 题目：请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子
 * 字符串的长度。假设字符串中只包含从'a'到'z'的字符。
 * @version: 1.0
 */
public class LongestSubstringWithoutDup {
    // 方法一：蛮力法
    public static int longestSubstringWithoutDuplication(String string){
        if(string == null)
            return 0;

        int[] position = new int[26];
        int maxLength = 0;

        for(int start=0; start<string.length(); start++)
            for(int end=start; end<=string.length(); end++){
                String substring = string.substring(start,end);
                if(!hasDuplication(substring, position))
                    maxLength = Math.max(substring.length(), maxLength);
            }
        return maxLength;
    }  // end method

    private static boolean hasDuplication(String substring, int[] position){
        for(int i=0; i<position.length; i++)
            position[i] = -1;

        for(int j=0; j<substring.length(); j++){
            int charIndex = substring.charAt(j)-'a';
            if(position[charIndex] != -1)
                return true;

            position[charIndex] = j;
        }
        return false;
    }  // end hasDuplication()


    // 方法二：动态规划提高时间效率
    public static int longestSubstringWithoutDuplication2(String string){
        if(string == null)
            return 0;

        int[] position = new int[26];
        for(int i=0; i<26; i++)
            position[i] = -1;

        int maxLength = 0;
        int curLength = 0;  // f(i-1)，记录以i-1位置处字符结尾的不包含重复字符串的最长长度

        for(int i=0; i<string.length(); i++){
            int charIndex = string.charAt(i)-'a';
            int preIndex = position[charIndex];

            if(preIndex<0 || i-preIndex>curLength)  // 当前字符之前没出现过，或出现过且比上个字符之前的重复值还靠前
                curLength++;
            else{  // 当前字符之前出现过，但比上个字符之前的重复值靠后
                if(curLength > maxLength)  // 在以上个字符结尾的不包含重复字符串的最长长度被覆盖之前，判断是否更新最大长度
                    maxLength = curLength;

                curLength = i - preIndex;
            }
            position[charIndex] = i;  // 记录当前字符出现的位置
        }  // end for

        if(curLength > maxLength)  // 在结束前，比较最后以一个字符结尾的不包含重复字符串的最长长度和最大长度，判断是否更新最大长度
            maxLength = curLength;
        return maxLength;
    }  // end method

}  // end class
